#include <stdio.h>
#include <stdlib.h>

#define ElementType int
#define Cutoff 100

void bubble_Sort(ElementType *a, int n);
void insertion_Sort(ElementType *a, int n);
void merge_Sort(ElementType a[], int length);
void heap_Sort(ElementType a[], int length);
void shell_Sort(ElementType a[], int length);
void quick_Sort(ElementType a[], int length);

void printArray(int a[], int n);
void inputArray(int a[], int n);

int qsort_comparator(const void *e1, const void *e2) {
    ElementType a1 = *(ElementType*)e1;
    ElementType a2 = *(ElementType*)e2;
    return a1 - a2;
}
int main() {
    int n;
    scanf("%d", &n);
    ElementType *a = malloc(n * sizeof(ElementType));
    inputArray(a, n);

    // bubble_Sort(a, n); // 测试 4,8超时，测试6 7015
    // insertion_Sort(a, n); // 测试6 3015
    // merge_Sort(a, n); // 测试6 36
    // heap_Sort(a, n);
    // shell_Sort(a, n);
    // quick_Sort(a, n);
    qsort(a, n, sizeof(ElementType), qsort_comparator);
    printArray(a, n);
}

/* base function ====================================*/
void swap(ElementType *a, ElementType *b) {
    ElementType t;
    t = *a;
    *a = *b;
    *b = t;
}

int comparator(ElementType a, ElementType b) {
    if (a > b) {
        return 1;
    } else if (a < b) {
        return -1;
    } else {
        return 0;
    }
}

// 打印空格分隔的，结尾无空格的数组
void printArray(int a[], int n) {
    if (n < 1 || a == NULL) {
        return;
    }
    printf("%d", *a++);
    for (int i=1; i<n; i++) {
        printf(" %d", *a++);
    }
    printf("\n");
}

void inputArray(int a[], int n) {
    for (int i=0; i<n; i++, a++) {
        scanf("%d", a);
    }
}

/* Buble =================================*/
void bubble_Sort(ElementType a[], int length) {
    // 排序 P 次
    for (int p=length-1; p >= 0; p--) {
        int flag = 0;
        for (int i=0; i < p; i++) {
            // 一趟冒泡
            if (comparator(a[i], a[i+1]) > 0) {
                swap(&a[i], &a[i+1]);
                flag = 1; // 标识发生了交换
            }
        }
        if (flag == 0) {
            // 全程无交换
            break;
        }
    }
}

/* Insertion ================================*/
// 从第 P 趟开始继续排
void insertion_Sort_Pass(ElementType a[], int p, int length) {
    ElementType tmp = a[p]; // 下一个待排序的数
    int i;
    for (i=p; i > 0 && comparator(a[i-1], tmp) > 0; i--) {
        a[i] = a[i-1]; // 移出空位
    }
    // 插入
    a[i] = tmp;
}

void insertion_Sort(ElementType a[], int length) {
    // 执行 p-1 次
    for (int p=1; p < length; p++) {
        insertion_Sort_Pass(a, p, length);
    }
}


/* merge ===================================*/
// 合并两个有序数组
void merge(ElementType a[], ElementType temp[], int leftStart, int rightStart, int rightEnd) {
    // 左边起点
    int left = leftStart;
    // 左边终点
    int leftEnd = rightStart - 1;
    // 右边起点
    int right = rightStart;
    // 临时数组的下标
    int tempIndex = leftStart;
    
    // 两个数组都有元素
    while (left <= leftEnd && right <= rightEnd) {
        if (comparator(a[left], a[right]) <= 0) {
            temp[tempIndex++] = a[left++];
        } else {
            temp[tempIndex++] = a[right++];
        }
    }
    // 左边有剩余
    while (left <= leftEnd) {
        temp[tempIndex++] = a[left++];
    }
    // 右边有剩余
    while (right <= rightEnd) {
        temp[tempIndex++] = a[right++];
    }
}

void merge_pass(ElementType a[], ElementType temp[], int length, int step) {
    int i;
    for (i=0; i < length - 2 * step; i += 2*step) {
        // 左边起点
        int leftStart = i;
        // 右边起点
        int rightStart = i + step;
        // 右边终点
        int rightEnd = i + 2*step - 1;
        // 合并
        merge(a, temp, leftStart, rightStart, rightEnd);
    }
    if (i + step < length) {
        // 归并最后2个子列
        merge(a, temp, i, i + step, length-1);
    } else {
        // 只剩下1个子列
        for (int j=i; j < length; j++) {
            temp[j] = a[j];
        }
    }
}

// 非递归实现的 merge 排序算法
void merge_Sort(ElementType a[], int length) {
    // 临时数组
    ElementType *temp = malloc(sizeof(ElementType) * length);
    // 从 1 到 length/2 为步长，两两合并
    for (int step=1; step < length; ) {
        merge_pass(a, temp, length, step);
        step *= 2;
        merge_pass(temp, a, length, step);
        step *= 2;
    }
    free(temp);
}

/* heap sort =========================================*/
// 从 startIdx 开始的位置向下调整，让数组变为堆
void percDown(ElementType a[], int startIdx, int length) {
    int parent, child;
    // 取出 startIdx 处存放的值
    ElementType temp = a[startIdx];
    // 向下（左右儿子）找可以正确存放 temp 的合适位置
    for (parent = startIdx; parent*2+1 < length; parent = child /* 顺着调整过的儿子节点继续向下 */) {
        child = parent*2+1;
        if ((child != length - 1) && comparator(a[child], a[child+1]) < 0) {
            // 有右儿子，且右儿子比较大
            child++; // 指向右儿子
        }
        if (comparator(temp, a[child]) >= 0) {
            // temp 比它的左右儿子都大，即找到了合适位置，不用再往下找了
            break;
        }
        // 把更大的子节点复制到父节点位置，即把大的数往上调
        a[parent] = a[child];
    }
    a[parent] = temp;
}

// 堆排序, 选择排序的一种，先建立最大堆，然后把堆顶元素和最后一个元素交换，然后把剩下的元素重新调整为最大堆，重复这个过程
void heap_Sort(ElementType a[], int length) {
    // 建立最大堆
    for (int i=length/2; i >= 0; i--) {
        percDown(a, i, length);
    }
    // 排序
    for (int i=length-1; i > 0; i--) {
        // 把堆顶元素和最后一个元素交换
        swap(&a[0], &a[i]);
        percDown(a, 0, i);
    }
}

/* shell sort =========================================*/
void shell_Sort(ElementType a[], int length) {
    int sedgewickStepArr[] = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929,
        16001, 36289, 64769, 146305, 260609, 587521, 1045505, 2354689, 4188161,
        9427969, 16764929, 37730305, 67084289, 150958081, 268386305, 603906049,
        1073643521};
    int sedgewickStepArrLen = 28;
    int i, j, k, step;
    ElementType tmp;
    // 初始增量不能超出数组长度
    for (k = 0; length > sedgewickStepArr[k]; k++) {
        ;
    }
    for (; k >= 0; k--) {
        step = sedgewickStepArr[k];
        // 插入排序
        for (i = step; i < length; i++) {
            tmp = a[i];
            for (j = i; j >= step && comparator(tmp, a[j - step]) < 0; j -= step) {
                a[j] = a[j - step];
            }
            a[j] = tmp;
        }
    }
}


/* quick sort =========================================*/
ElementType median3(ElementType a[], int left, int right) {
    int center = (left + right) / 2;
    if (comparator(a[left], a[center]) > 0) {
        swap(&a[left], &a[center]);
    }
    if (comparator(a[left], a[right]) > 0) {
        swap(&a[left], &a[right]);
    }
    if (comparator(a[center], a[right]) > 0) {
        swap(&a[center], &a[right]);
    }
    // 将基准元素藏在右边
    swap(&a[center], &a[right-1]);
    return a[right-1];
}

// 快速排序算法
void quick_Sort(ElementType a[], int length) {
    if (length <= 1) {
        return;
    }
    if (length < Cutoff) {
        // 小数组使用插入排序
        heap_Sort(a, length);
        return;
    }
    // 选取基准元素
    ElementType pivot = median3(a, 0, length-1);
    // 将小于基准的元素放在左边，大于基准的元素放在右边
    // 原本 int left = 0, right = length - 1;
    // 因为做 median3 时，最小元素已经放在了 a[0], 最大元素放在了 a[length-1]
    // pivot 放在了 a[length-1]
    int left = 1, right = length - 2;
    while (left < right) {
        while (left < right && comparator(a[left], pivot) <= 0) {
            left++;
        }
        while (left < right && comparator(a[right], pivot) >= 0) {
            right--;
        }
        if (left < right) {
            swap(&a[left], &a[right]);
        }
    }
    // 将基准元素放在中间
    swap(&a[left], &a[length-2]);
    // 递归处理左右两边
    quick_Sort(a, left);
    quick_Sort(a+left+1, length-left-1);
}
